package mathMethod;

import java.util.Random;

public class LinkRandom {

    /**
     * LeetCode T382 链表随机节点
     *
     * @param args
     */
    public static void main(String[] args) {

    }
}



class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution3 {

    private ListNode head;

    /** @param head The linked list's head.
    Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution3(ListNode head) {
        this.head = head;
    }

    /** Returns a random node's value. */
    public int getRandom() {
        ListNode node = head;
        int n = 1;
        int res = node.val;
        node = node.next;
        while (node != null){
            n++;
            double random = Math.random();
            if (random < (double)1/n){
                res = node.val;
            }
            node = node.next;
        }
        return res;

    }
}
